package com.cctc.juc.source.Bitc.Icontainer.hash;

import sun.misc.Unsafe;

import java.util.AbstractMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.locks.ReentrantLock;

/**
 * [ConcurrentHashMap（JDK 7）线程安全的哈希表]
 * 要求：熟练掌握（手撕、陈述）ConcurrentHashMap [（JDK 7）线程安全的哈希表] 核心（主干）实现逻辑。
 * 概述：JDK 7 中的 ConcurrentHashMap 是一个基于 Segment（段、数据分片）数组构建的线程安全的哈希表，将 HashTable 中的表级锁优化成了分段锁，默认并发级别（初始 Segment 段容量，无法实现动态调整）为 16，即默认支持 16 个线程并发操作。
 * Segment 子类继承自 ReentrantLock，内部是一个基于 HashEntry 数组构建的子哈希表，类似于一个 HashMap 子数组，然后通过 ReentrantLock 控制每个子哈希表的互斥操作，所有 Segment 片段构建的 Segment 数组组成了整个线程安全的哈希表，即解决了哈希表的线程安全问题，又提升了并发量。
 * 补充知识点：Segment 内部类的实现思路与线程池中的 Worker 内部类有点类似，二者同样继承于 JUC 显式锁，Segment 继承自 ReentrantLock，而 Worker 直接继承自 AQS 基类，均具备线程同步能力，以此来保证各自内部临界区代码段的互斥执行；实现场景上，Segment 实例保护的是内部基于 HashEntry 数组构建的子哈希表的互斥操作，而 Worker 实例保护的是线程池并发任务的（执行前 -> 执行中 -> 执行后）原子执行。
 */
public abstract class CC7HMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {
    /**
     * [HashEntry 数据节点（数据模型）] 内部类。
     * - 单向链表，只有 next 后继节点。
     */
    static final class HashEntry<K, V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K, V> next;

        public HashEntry(int hash, K key, V value, HashEntry<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        final void casNext(HashEntry<K, V> next) {
            UNSAFE.putOrderedObject(this, nextOffset, next);
        }

        static final Unsafe UNSAFE = Unsafe.getUnsafe();
        static final long nextOffset;

        static {
            Class<HashEntry> hashEntryClass = HashEntry.class;
            try {
                nextOffset = UNSAFE.objectFieldOffset(hashEntryClass.getDeclaredField("next"));
            } catch (NoSuchFieldException e) {
                throw new RuntimeException(e);
            }
        }

    }

    /**
     * [Segment 数据片段（数据模型）] 内部类。
     */
    static final class Segment<K, V> extends ReentrantLock {
        volatile transient HashEntry<K, V>[] table;
        transient int size;
        final float loadFactor;
        transient int threshold;
        transient int modCount;

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4, MAXIMUM_CAPACITY = 1 << 30;
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

        Segment(HashEntry<K, V>[] table, float loadFactor, int threshold) {
            this.table = table;
            this.loadFactor = loadFactor;
            this.threshold = threshold;
        }

        /**
         * 以（线程安全）写（插入 | 更新）操作为例，进行分析。
         * 核心（实现）逻辑：
         * 1）加锁；
         * 2）基于关键字 key 的哈希值，定位目标节点在 table 数组中的位置（下标），获取根节点；
         * 3）遍历链表，寻找目标更新节点：
         * 4）如果目标节点不存在，则创建一个新节点，基于 CAS 操作以线程安全的方式插入到链表头部，作为新插入节点；
         * - 如果数组大小（Node 节点数量）超过了扩容阈值，调用 resize() 方法，执行扩容操作；
         * - 维护写版本号；
         * - 结束遍历，走 6）；
         * 5）如果目标节点存在，则更新目标节点的值，并维护写版本号，结束遍历，走 6）；
         * 6）解锁；
         * 7）如果是插入操作，返回 null；如果是更新操作，返回旧元素值。
         *
         * @param key          关键字
         * @param hash         关键字 key 的散列值
         * @param value        元素值
         * @param onlyIfAbsent 是否仅执行插入操作？
         * @return 如果是插入操作，返回 null；如果是更新操作，返回旧元素值。
         */
        final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            /**
             * 加锁。
             * - scanAndLockForPut()，在尝试获取锁失败时扫描包含给定密钥的节点，如果找不到，则创建并返回一个，返回时，保证锁被持有。
             */
            HashEntry<K, V> target = tryLock() ? null : scanAndLockForPut(key, hash, value);
            V oldValue;
            try {
                HashEntry<K, V>[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K, V> parent = entryAt(tab, index);
                // “自旋” 写操作，直到成功。
                for (HashEntry<K, V> entry = parent; ; ) {
                    if (entry != null) {
                        // 更新操作
                        K k;
                        if (entry.hash == hash && ((k = entry.key) == key || (key != null && key.equals(k)))) {
                            oldValue = entry.value;
                            if (!onlyIfAbsent || oldValue == null) {
                                entry.value = value;
                                modCount++;
                            }
                            break;
                        }
                        entry = entry.next;
                    } else {
                        // 插入操作
                        if (target != null) target.casNext(parent);
                        else target = new HashEntry<>(hash, key, value, parent);
                        if (++size > threshold && tab.length < MAXIMUM_CAPACITY) {
                            rehash(target);
                        } else setEntryAt(tab, index, target);
                        modCount++;
                        oldValue = null;
                        break;
                    }
                }
            } finally {
                // 解锁
                unlock();
            }
            // 返回旧元素值
            return oldValue;
        }
    }

    final Segment<K, V>[] segments;

    static final int DEFAULT_CONCURRENCY_LEVEL = 1 << 4;
    static final int MIN_SEGMENT_TABLE_CAPACITY = 2, MAX_SEGMENTS = 1 << 16;

    /**
     * 构造器。
     * - 伪代码，仅用于分析核心（主干）逻辑。
     * 1）参数校验；
     * 2）初始化 Segment 段数组。
     */
    public CC7HMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
        if (initialCapacity < 0 || loadFactor <= 0 || concurrencyLevel <= 0) throw new IllegalArgumentException();
        if (concurrencyLevel > MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS;
        // ... ...
        this.segments = new Segment[initialCapacity];
    }

    /**
     * 以（线程安全）写（插入 | 更新）操作方法为例，分析 ConcurrentHashMap [JDK 7] 底层线程同步原理。
     * 核心（实现）逻辑：
     * 1）基于关键字 key 的散列值，找到目标段在 Segment 段数组中的位置（下标），获取目标段；
     * 2）调用目标段的 put() 方法，以线程安全的方式执行写（插入 | 更新）操作。
     * 2.1）加锁；
     * 2.2）基于关键字 key 的哈希值，定位目标节点在 table 数组中的位置（下标），获取根节点；
     * 2.3）遍历链表，寻找目标更新节点：
     * 2.4）如果目标节点不存在，则创建一个新节点，基于 CAS 操作以线程安全的方式插入到链表头部，作为新插入节点；
     * - 如果数组大小（Node 节点数量）超过了扩容阈值，调用 resize() 方法，执行扩容操作；
     * - 维护写版本号；
     * - 结束遍历，走 2.6）；
     * 2.5）如果目标节点存在，则更新目标节点的值，并维护写版本号，结束遍历，走 2.6）；
     * 2.6）解锁；
     * 2.7）如果是插入操作，返回 null；如果是更新操作，返回旧元素值。
     */
    public V put(K key, V value) {
        Segment<K, V> segment;
        if (value == null) throw new NullPointerException();
        int hash = key.hashCode();
        int h = (hash >>> segmentShift) & segmentMask;
        long offset = (h << SSHIFT) + SBASE;
        segment = UNSAFE.getObject(segments, offset);
        return segment.put(key, hash, value, false);
    }

    // ... ...


}
